package tree;
//https://leetcode.cn/leetbook/read/illustration-of-algorithm/lhxstd/
//给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
//
//百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，
// 满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。
/**
 * 二叉搜索树的特点：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
 * 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值
 */
public class 求二叉搜索树的最近公共祖先 {
      public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }
  //迭代
    class Solution {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if(p.val > q.val){
                TreeNode tmp = p;
                p = q;
                q = tmp;
            }
            while (root != null){
                if(root.val < p.val)
                    root = root.right;
                else if(root.val > q.val)
                    root = root.left;
                else break;
            }
            return root;
        }
    }
    //递归
    class Solution2 {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if(root.val < p.val && root.val < q.val)
                return lowestCommonAncestor(root.right,p,q);
            if(root.val > p.val && root.val > q.val)
                return  lowestCommonAncestor(root.left, p, q);
            return root;
        }
    }
}
